home *** CD-ROM | disk | FTP | other *** search
/ Aminet 23 / Aminet 23 (1998)(GTI - Schatztruhe)[!][Feb 1998].iso / Aminet / misc / emu / amiSPIMsrc.lha / sym-tbl.c < prev    next >
C/C++ Source or Header  |  1994-01-17  |  11KB  |  518 lines
  1. /* SPIM S20 MIPS simulator.
  2.    Code to maintain symbol table to resolve symbolic labels.
  3.    Copyright (C) 1990-1994 by James Larus (larus@cs.wisc.edu).
  4.    ALL RIGHTS RESERVED.
  5.  
  6.    SPIM is distributed under the following conditions:
  7.  
  8.      You may make copies of SPIM for your own use and modify those copies.
  9.  
  10.      All copies of SPIM must retain my name and copyright notice.
  11.  
  12.      You may not sell SPIM or distributed SPIM in conjunction with a
  13.      commerical product or service without the expressed written consent of
  14.      James Larus.
  15.  
  16.    THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.    IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.    WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19.    PURPOSE. */
  20.  
  21.  
  22. /* $Header: /home/primost/larus/Software/SPIM/RCS/sym-tbl.c,v 3.14 1994/01/18 03:21:45 larus Exp larus $
  23. */
  24.  
  25.  
  26.  
  27. #include "spim.h"
  28. #include "spim-utils.h"
  29. #include "inst.h"
  30. #include "mem.h"
  31. #include "data.h"
  32. #include "parser.h"
  33. #include "sym-tbl.h"
  34.  
  35.  
  36. /* Local functions: */
  37.  
  38. #ifdef __STDC__
  39. static void get_hash (char *name, int *slot_no, label **entry);
  40. static void resolve_label_uses (label *sym);
  41. static void resolve_a_label_sub (label *sym, instruction *inst, mem_addr pc);
  42. #else
  43. static void get_hash ();
  44. static void resolve_label_uses ();
  45. static void resolve_a_label_sub ();
  46. #endif
  47.  
  48.  
  49.  
  50. /* Keep track of the memory location that a label represents.  If we
  51.    see a reference to a label that is not yet defined, then record the
  52.    reference so that we can patch up the instruction when the label is
  53.    defined.
  54.  
  55.    At the end of a file, we flush the hash table of all non-global
  56.    labels so they can't be seen in other files.     */
  57.  
  58.  
  59. static label *local_labels = NULL; /* Labels local to current file. */
  60.  
  61.  
  62. #define HASHBITS 30
  63.  
  64. #define LABEL_HASH_TABLE_SIZE 8191
  65.  
  66.  
  67. /* Map from name of a label to a label structure. */
  68.  
  69. static label *label_hash_table [LABEL_HASH_TABLE_SIZE];
  70.  
  71.  
  72. /* Initialize the symbol table by removing and freeing old entries. */
  73.  
  74. #ifdef __STDC__
  75. void
  76. initialize_symbol_table (void)
  77. #else
  78. void
  79. initialize_symbol_table ()
  80. #endif
  81. {
  82.   register int i = LABEL_HASH_TABLE_SIZE;
  83.   register label **l = label_hash_table;
  84.  
  85.   for ( ; i > 0; i--, l ++)
  86.     {
  87.       register label *x, *n;
  88.  
  89.       for (x = *l; x != NULL; x = n)
  90.     {
  91.       free (x->name);
  92.       n = x->next;
  93.       free (x);
  94.     }
  95.       *l = NULL;
  96.     }
  97.   local_labels = NULL;
  98. }
  99.  
  100.  
  101.  
  102. /* Lookup for a label with the given NAME.  Set the SLOT_NO to be the hash
  103.    table bucket that contains (or would contain) the label's record.  If the
  104.    record is already in the table, set ENTRY to point to it.  Otherwise,
  105.    set ENTRY to be NULL. */
  106.  
  107. #ifdef __STDC__
  108. static void
  109. get_hash (char *name, int *slot_no, label **entry)
  110. #else
  111. static void
  112. get_hash (name, slot_no, entry)
  113.      char *name;
  114.      int *slot_no;
  115.      label **entry;
  116. #endif
  117. {
  118.   register int hi;
  119.   register int i;
  120.   register label *lab;
  121.   register int len;
  122.  
  123.   /* Compute length of name in len.  */
  124.   for (len = 0; name[len]; len++);
  125.  
  126.   /* Compute hash code */
  127.   hi = len;
  128.   for (i = 0; i < len; i++)
  129.     hi = ((hi * 613) + (unsigned)(name[i]));
  130.  
  131.   hi &= (1 << HASHBITS) - 1;
  132.   hi %= LABEL_HASH_TABLE_SIZE;
  133.  
  134.   *slot_no = hi;
  135.   /* Search table for entry */
  136.   for (lab = label_hash_table [hi]; lab; lab = lab->next)
  137.     if (streq (lab->name, name))
  138.       {
  139.     *entry = lab;        /* <-- return if found */
  140.     return;
  141.       }
  142.   *entry = NULL;
  143. }
  144.  
  145.  
  146. /* Lookup label with NAME.  Either return its symbol table entry or NULL
  147.    if it is not in the table. */
  148.  
  149. #ifdef __STDC__
  150. label *
  151. label_is_defined (register char *name)
  152. #else
  153. label *
  154. label_is_defined (name)
  155.      register char *name;
  156. #endif
  157. {
  158.   int hi;
  159.   label *entry;
  160.  
  161.   get_hash (name, &hi, &entry);
  162.  
  163.   return (entry);
  164. }
  165.  
  166.  
  167. /* Return a label with a given NAME.  If an label with that name has
  168.    previously been looked-up, the same node is returned this time.  */
  169.  
  170. #ifdef __STDC__
  171. label *
  172. lookup_label (register char *name)
  173. #else
  174. label *
  175. lookup_label (name)
  176.      register char *name;
  177. #endif
  178. {
  179.   int hi;
  180.   label *entry, *lab;
  181.  
  182.   get_hash (name, &hi, &entry);
  183.  
  184.   if (entry != NULL)
  185.     return (entry);
  186.  
  187.   /* Not found, create one, add to chain */
  188.   lab = (label *) xmalloc (sizeof (label));
  189.   lab->name = str_copy (name);
  190.   lab->addr = 0;
  191.   lab->global_flag = 0;
  192.   lab->const_flag = 0;
  193.   lab->gp_flag = 0;
  194.   lab->uses = NULL;
  195.  
  196.   lab->next = label_hash_table [hi];
  197.   label_hash_table [hi] = lab;
  198.   return lab;            /* <-- return if created */
  199. }
  200.  
  201.  
  202. /* Record that the label named NAME refers to ADDRESS.    Return the label
  203.    structure. */
  204.  
  205. #ifdef __STDC__
  206. label *
  207. record_label (char *name, mem_addr address)
  208. #else
  209. label *
  210. record_label (name, address)
  211.      char *name;
  212.      mem_addr address;
  213. #endif
  214. {
  215.   label *l = lookup_label (name);
  216.  
  217.   free (name);
  218.   if (!l->gp_flag)
  219.     {
  220.       if (l->addr != 0)
  221.     {
  222.       yyerror ("Label is defined for the second time");
  223.       return (l);
  224.     }
  225.       l->addr = address;
  226.     }
  227.   resolve_label_uses (l);
  228.   l->uses = NULL;
  229.   if (!l->global_flag)
  230.     {
  231.       l->next_local = local_labels;
  232.       local_labels = l;
  233.     }
  234.   return (l);
  235. }
  236.  
  237.  
  238. /* Make the label named NAME global.  Return its symbol. */
  239.  
  240. #ifdef __STDC__
  241. label *
  242. make_label_global (char *name)
  243. #else
  244. label *
  245. make_label_global (name)
  246.      char *name;
  247. #endif
  248. {
  249.   label *l = lookup_label (name);
  250.  
  251.   free (name);
  252.   l->global_flag = 1;
  253.   return (l);
  254. }
  255.  
  256.  
  257. /* Record that an INSTRUCTION uses the as-yet undefined SYMBOL. */
  258.  
  259. #ifdef __STDC__
  260. void
  261. record_inst_uses_symbol (instruction *inst, label *sym)
  262. #else
  263. void
  264. record_inst_uses_symbol (inst, sym)
  265.      instruction *inst;
  266.      label *sym;
  267. #endif
  268. {
  269.   label_use *u = (label_use *) xmalloc (sizeof (label_use));
  270.  
  271.   if (data_dir)            /* Want to free up original instruction */
  272.     {
  273.       u->inst = copy_inst (inst);
  274.       u->addr = current_data_pc ();
  275.     }
  276.   else
  277.     {
  278.       u->inst = inst;
  279.       u->addr = current_text_pc ();
  280.     }
  281.   u->next = sym->uses;
  282.   sym->uses = u;
  283. }
  284.  
  285.  
  286. /* Record that a memory LOCATION uses the as-yet undefined SYMBOL. */
  287.  
  288. #ifdef __STDC__
  289. void
  290. record_data_uses_symbol (mem_addr location, label *sym)
  291. #else
  292. void
  293. record_data_uses_symbol (location, sym)
  294.      mem_addr location;
  295.      label *sym;
  296. #endif
  297. {
  298.   label_use *u = (label_use *) xmalloc (sizeof (label_use));
  299.  
  300.   u->inst = NULL;
  301.   u->addr = location;
  302.   u->next = sym->uses;
  303.   sym->uses = u;
  304. }
  305.  
  306.  
  307. /* Given a newly-defined LABEL, resolve the previously encountered
  308.    instructions and data locations that refer to the label. */
  309.  
  310. #ifdef __STDC__
  311. static void
  312. resolve_label_uses (label *sym)
  313. #else
  314. static void
  315. resolve_label_uses (sym)
  316.      label *sym;
  317. #endif
  318. {
  319.   register label_use *use;
  320.   register label_use *next_use;
  321.  
  322.   for (use = sym->uses; use != NULL; use = next_use)
  323.     {
  324.       resolve_a_label_sub (sym, use->inst, use->addr);
  325.       if (use->inst != NULL && use->addr >= DATA_BOT && use->addr < stack_bot)
  326.     {
  327.       SET_MEM_WORD (use->addr, inst_encode (use->inst));
  328.       free_inst (use->inst);
  329.     }
  330.       next_use = use->next;
  331.       free (use);
  332.     }
  333. }
  334.  
  335.  
  336. /* Resolve the newly-defined label in INSTRUCTION. */
  337.  
  338. #ifdef __STDC__
  339. void
  340. resolve_a_label (label *sym, instruction *inst)
  341. #else
  342. void
  343. resolve_a_label (sym, inst)
  344.      label *sym;
  345.      instruction *inst;
  346. #endif
  347. {
  348.   resolve_a_label_sub (sym,
  349.                inst,
  350.                (data_dir ? current_data_pc () : current_text_pc ()));
  351. }
  352.  
  353.  
  354. #ifdef __STDC__
  355. static void
  356. resolve_a_label_sub (label *sym, instruction *inst, mem_addr pc)
  357. #else
  358. static void
  359. resolve_a_label_sub (sym, inst, pc)
  360.   label *sym;
  361.    instruction *inst;
  362.    mem_addr pc;
  363. #endif
  364. {
  365.   if (inst == NULL)
  366.     {
  367.       /* Memory data: */
  368.       SET_MEM_WORD (pc, sym->addr);
  369.     }
  370.   else
  371.     {
  372.       /* Instruction: */
  373.       if (EXPR (inst)->pc_relative)
  374.     EXPR (inst)->offset = -pc; /* Instruction may have moved */
  375.  
  376.       if (EXPR (inst)->symbol == NULL
  377.       || SYMBOL_IS_DEFINED (EXPR (inst)->symbol))
  378.     {
  379.       long value;
  380.       int mask;
  381.  
  382.       if (opcode_is_branch (OPCODE (inst)))
  383.         {
  384.           short val;
  385.  
  386.           /* Drop low two bits since instructions are on word
  387.          boundaries. */
  388.           val = eval_imm_expr (EXPR (inst));
  389.           val >>= 2;    /* Seperate to force sign-extension */
  390.  
  391. #ifdef CL_SPIM
  392.           if (cycle_level)
  393.         val -= 1;
  394.           else
  395. #endif
  396.  
  397.           if (bare_machine)    /* Delayed branch */
  398.         val -= 1;
  399.  
  400.           value = val;
  401.           mask = 0xffff;
  402.         }
  403.       else if (opcode_is_jump (OPCODE (inst)))
  404.         {
  405.           /* Drop low two bits since instructions are on word
  406.          boundaries. */
  407.           value = eval_imm_expr (EXPR (inst)) >> 2;
  408.           mask = 0x03fffffff;
  409.         }
  410.       else if (opcode_is_load_store (OPCODE (inst)))
  411.         {
  412.           /* Label's location is an address */
  413.           value = eval_imm_expr (EXPR (inst));
  414.           mask = 0xffff;
  415.         }
  416.       else
  417.         {
  418.           /* Label's location is a value */
  419.           value = eval_imm_expr (EXPR (inst));
  420.           mask = 0xffff;
  421.         }
  422.  
  423.       if ((value & ~mask) != 0 && (value & ~mask) != 0xffff0000)
  424.         {
  425.           error ("Immediate value is too large for field: ");
  426.           print_inst (pc);
  427.         }
  428.       if (opcode_is_jump (OPCODE (inst)))
  429.         TARGET (inst) = value; /* Don't mask so it is sign-extended */
  430.       else
  431.         IMM (inst) = value;    /* Ditto */
  432.       ENCODING (inst) = inst_encode (inst);
  433.     }
  434.       else
  435.     error ("Resolving undefined symbol: %s\n",
  436.            (EXPR (inst)->symbol == NULL) ? "" : EXPR (inst)->symbol->name);
  437.     }
  438. }
  439.  
  440.  
  441. /* Remove all local (non-global) label from the table. */
  442.  
  443. #ifdef __STDC__
  444. void
  445. flush_local_labels (void)
  446. #else
  447. void
  448. flush_local_labels ()
  449. #endif
  450. {
  451.   register label *l;
  452.  
  453.   for (l = local_labels; l != NULL; l = l->next_local)
  454.     {
  455.       int hi;
  456.       label *entry, *lab, *p;
  457.  
  458.       get_hash (l->name, &hi, &entry);
  459.  
  460.       for (lab = label_hash_table [hi], p = NULL;
  461.        lab;
  462.        p = lab, lab = lab->next)
  463.     if (lab == entry)
  464.       {
  465.         if (p == NULL)
  466.           label_hash_table [hi] = lab->next;
  467.         else
  468.           p->next = lab->next;
  469.         if (entry->addr == 0 && !entry->const_flag)
  470.           error ("Warning: local symbol %s was not defined\n",
  471.              entry->name);
  472.         /* Can't free label since IMM_EXPR's still reference it */
  473.         break;
  474.       }
  475.     }
  476.   local_labels = NULL;
  477. }
  478.  
  479.  
  480. /* Return the address of SYMBOL or 0 if it is undefined. */
  481.  
  482. #ifdef __STDC__
  483. mem_addr
  484. find_symbol_address (char *symbol)
  485. #else
  486. mem_addr
  487. find_symbol_address (symbol)
  488.      char *symbol;
  489. #endif
  490. {
  491.   label *l = lookup_label (symbol);
  492.  
  493.   if (l == NULL || l->addr == 0)
  494.     return 0;
  495.   else
  496.     return (l->addr);
  497. }
  498.  
  499.  
  500. /* Print all symbols in the table. */
  501.  
  502. #ifdef __STDC__
  503. void
  504. print_symbols (void)
  505. #else
  506. void
  507. print_symbols ()
  508. #endif
  509. {
  510.   register int i;
  511.   register label *l;
  512.  
  513.   for (i = 0; i < LABEL_HASH_TABLE_SIZE; i ++)
  514.     for (l = label_hash_table [i]; l != NULL; l = l->next)
  515.       write_output (message_out, "%s%s at 0x%08x\n",
  516.             l->global_flag ? "g\t" : "\t", l->name, l->addr);
  517. }
  518.